package org.example.everyday;

import org.example.ch04.tree.TreeNode;

/**
 * <p>
 * Description:TODO 详细描述
 * <p>
 * <p>
 *
 * @author anlu
 * @date 2022/6/2 0002 12:31
 */
public class Lc450 {
    public static void main(String[] args) {
        Lc450 lc450 = new Lc450();

//        ：root = [5,3,6,2,4,null,7], key = 3




        TreeNode node2 = new TreeNode(2,null,null);

        TreeNode node3 = new TreeNode(4,null,null);
        TreeNode node1 = new TreeNode(3,node2,node3);

        TreeNode node5 = new TreeNode(7,null,null);
        TreeNode node4 = new TreeNode(6,null,node5);


        TreeNode root = new TreeNode(5,node1,node4);
        TreeNode res = lc450.deleteNode(root,3);
        System.out.println(res.val);



    }

    public TreeNode deleteNode(TreeNode root, int key){
        //递归的终止条件
        if(root == null){
            return null;
        }
        //当前值大于key,说明目标值在左子树，去左子树去找
        if(root.val > key){
            root.left = deleteNode(root.left,key);
            return root;
        }
        //当前值小于key,说明目标值在右子树，去右子树去找
        if(root.val < key){
            root.right = deleteNode(root.right,key);
            return root;
        }

        if(root.val == key){
            if(root.left == null && root.right == null){
                return null;
            }
            if(root.right == null){
                return root.left;
            }
            if(root.left == null){
                return root.right;
            }
            TreeNode successor = root.right;
            while(successor.left != null){
                successor = successor.left;
            }

            root.right = deleteNode(root.right,successor.val);
            successor.right = root.right;
            successor.left = root.left;

            return successor;

        }
        return root;

    }

}
